1. Field of the Invention
The invention relates generally to navigation systems and industrial control systems and more specifically to combinations of navigation and industrial controls that provide centimeter accuracy in the positioning and movement of operating machinery and robots.
2. Description of the Prior Art
When originally conceived, the global positioning system (GPS) that was made operational by the United States Government was not foreseen as being able to provide centimeter-level position accuracies. Such accuracies are now commonplace.
Extremely accurate GPS receivers depend on phase measurements of the radio carriers that they receive from various orbiting GPS satellites. Less accurate GPS receivers simply develop the pseudoranges to each visible satellite based on the time codes being sent. Within the granularity of a single time code, the carrier phase can be measured and used to compute range distance as a multiple of the fundamental carrier wavelength. GPS signal transmissions are on two synchronous, but separate, carrier frequencies "L1" and "L2", with wavelengths of nineteen and twenty-four centimeters, respectively. Thus within nineteen or twenty-four centimeters, the phase of the GPS carrier signal will change 360.degree..
However, the number of whole cycle (360.degree.) carrier phase shifts between a particular GPS satellite and the GPS receiver must be resolved. At the receiver, every cycle will appear the same. Therefore there is an "integer ambiguity". The computational resolution of the integer ambiguity has traditionally been an intensive arithmetic problem for the computers used to implement GPS receivers. The traditional approaches to such integer ambiguity resolution have prevented on-the-fly solution measurement updates for moving GPS receivers with centimeter accurate outputs. Very often, such highly accurate GPS receivers have required long periods of motionlessness to produce a first and subsequent position fix.
A prior art method for precision attitude determination and kinematic positioning is described by Hatch, in U.S. Pat. No. 4,963,889, comprises the steps of determining the approximate initial relative position of a secondary antenna that is freely movable with respect to a reference antenna; making carrier phase measurements based on the reception of "N" number of satellites, where N is the minimum number of satellites needed to compute the relative position of the secondary antenna; deriving from the carrier phase measurements an initial set of potential solutions for the relative position, wherein the initial set of potential solutions all fall within a region of uncertainty defined by a sphere having a radius equal to the maximum distance between the two antennas, and wherein multiple potential solutions arise because of whole-cycle ambiguity of the carrier signal; making redundant carrier phase measurements based on the reception of a carrier signal from an additional satellite (N+1); and eliminating false solutions from the initial set of potential solutions, based on a comparison of the redundant carrier phase measurements with the initial set of potential solutions, to reduce the number of potential solutions to close to one, whereby the number of potential solutions is not increased by use of the redundant carrier phase measurements.
"Deriving from the carrier phase measurements an initial set of potential solutions" means that the initial set is derived from just two satellites. The rest of the Hatch specification explains why N is exactly two in the case of attitude determination. Planar intersections of wave fronts are formed from the two satellites, thus obtaining a collection of parallel lines. The intersection points of these lines and a baseline sphere are determined, producing the initial set of potential solutions. For example, as explained at column 12, line 35 of Hatch, there are 188 points or potential solutions in the initial set. In the Hatch method, "eliminating false solutions from the initial set of potential solutions," means eliminating 187 of those 188 points. The idea of potential solutions refers to the initial set of 188 points.
Hatch forms an initial collection of around 188 potential solutions using just two satellites, and then uses phase measurements of the remaining satellites to whittle away at that the small initial collection, leaving only one candidate solution if phase measurements are accurate enough. Hatch avoids having to deal with large numbers of integer combinations.
Donald Knight, in U.S. Pat. No. 5,296,861, titled "METHOD AND APPARATUS FOR MAXIMUM LIKELIHOOD ESTIMATION DIRECT INTEGER SEARCH IN DIFFERENTIAL CARRIER PHASE ATTITUDE DETERMINATION SYSTEMS", and incorporated herein by reference, describes a method of reducing the mathematical intensity of integer ambiguity resolution.
Aside from making carrier phase measurements and determining a region of uncertainty, Hatch's method is essentially a two-step method, which is a way to avoid the problem of large numbers. The essence of the Knight patent is to do the opposite, plunging into a sea of possible solutions, even if there are trillions of them, and finding the single, best solution out of the entire product space of possibilities.
If ten different whole cycle values can be added to the first difference phase measurements from each of four satellites, then Knight defines 10.sup.4 or 10,000 possible acceptable solutions. Knight then finds the one-and-only solution out of 10,000 that matches the measured phase data better than all 9,999 other combinations. If eight satellites are available (which does happen), then Knight finds the single best solution out of 10.sup.8 or 100 million possibilities. If two antenna pairs are present, then the number becomes (10.sup.8).sup.2 =10.sup.16. Thus whereas Hatch uses a two-step method of avoiding large numbers, Knight provides a practical method for finding the single best solution in a solution space with thousands or millions of possibilities. Hatch even suggests that the Knight approach is incorrect. For example, at column 8, Line 63, Hatch states: "if ten different whole cycle values can be added to the first differences from each of the four satellites, then one might expect 103 or 10,000 possible solutions within the uncertainty region . . . Indeed, some authors have defined the number of possible acceptable solutions in exactly this fashion."
Knight describes a method that is more computationally intensive than Hatch's, and has proven to be reliable and workable in commercially-viable applications. Hatch's method avoids the problem of large numbers, and does best under conditions in which the problem of large numbers does not exist, e.g., under conditions where the myriad of possible solutions collapse into a handful. In the real world, conditions are usually not optimum, which would require the corresponding equipment that uses Hatch's method to be more complex, in order to achieve the same results as the present invention's.
Hatch's two-step method includes preliminary steps involving making carrier phase measurements, and then numbering them one through N, followed by an (N+1).sup.th measurement. It could be expected that any similar apparatus will make carrier phase measurements, and the basic idea of interferometry is conventional, regardless of how the carrier phase measurements are numbered. Such preliminary steps define which carrier phase measurements are involved in generating an initial set of potential solutions, and which carrier phase measurement is defined to be the redundant measurement for eliminating potential solutions. As applied to attitude determination, the step of determining the approximate relative position of the secondary antenna equates to measuring the distance between the antennas, and noticing that the secondary antenna has to lie on a sphere centered at the main antenna.
Hatch's method involving a "plurality N of satellites" is not the same as a "plurality of satellites". As applied to attitude determination, N is exactly two. As applied to kinematic surveying, N is exactly four. Hatch makes this explicit in FIG. 7, blocks 58 and 62, and states at column 12, line 3, "The first computations to be performed in an attitude determination application are to compute the entire set of potential solutions based on the carrier phase measurements from two satellites." One of the significant features of the method described is the use of only two of the satellites to determine the set of potential solutions, rather than more than two satellites. Hatch explains that only a plurality of N=2 satellites are required " . . . in the attitude determination application, . . . there is! only a two dimensional uncertainty region corresponding to the surface . . . Thus only two satellites are needed to define all the potential solutions that can exist on the two dimensional uncertainty region . . . The attitude detection application is a two dimensional uncertainty problem, requiring two satellites to define all of the potential solutions . . . The final broad step in the method of the invention is eliminating false potential solutions based on redundant information from additional satellites, i.e. additional to the minimum two . . . satellites required to define all of the potential solutions."
The phrases "initial set", "initial set of potential solutions" and "possible solution", refer specifically to the result obtainable by applying the first step of Hatch's two-step method. This "initial set of potential solutions" is to be generated from the received carrier signals of two and only two satellites, since the teaching is that "only two satellites are required to define all of the potential solutions."
The notion of "potential solutions" is thus restricted to 188 points, or to some such number in a similar example, but certainly not 10,000 solutions. It is also very clear that "eliminating false solutions from the initial set of potential solutions" means eliminating 187 points out of 188 points.
Hatch contends that it is not necessary to consider 10,000 possible solutions, because "the uncertainty region is two dimensional" and the measurements from any two satellites span the region of uncertainty. Using two satellites results in a collection of only 188 possibilities. Hatch contends that the correct solution is one of those 188 points, and that those 188 points are the only possibilities, that those other myriad of possibilities do not exist.
The "initial set of potential solutions" of Hatch cannot be extended to cover an entire product space of 10,000 solutions, because the essence of the two-step method is avoiding the problem of large numbers. Hatch proposes reducing the dimensionally of the solution space to the bare minimum and declares that the right answer has to lie within that reduced solution space, and that only the first measurements corresponding in number to the bare dimensionally are required to determine all the possible solutions.
Knight does not include an initial set. The method of Knight is to search for the right answer somewhere among 10,000 possibilities and finds the single best match out of such possibilities. There is no reason to stop and look at 188 possibilities when the remainder of 10,000 possibilities have to be searched. Furthermore, those 188 possibilities defined by Hatch do not resemble anything in Knight. Knight does not involve deriving from the carrier phase measurements an initial set of potential solutions for the relative position. Furthermore, Hatch generates those 188 points using a nonlinear operation on the carrier phase measurements of two satellites, something that Knight does not.
Hatch eliminates false solutions from the initial set of potential solutions, whereby the number of potential solutions is not increased by use of the redundant carrier phase measurements. Knight does not deal with Hatch's "initial set", whether to create it or eliminate from it. Most of the time, in a commercially-viable apparatus, the right solution will not be found in such an initial set.
If carrier phases could be measured perfectly, without radio reflections, reception noise, non-common antenna phase center motion, temperature sensitive drifts and other corruption of the measured phase data, then the attitude determination problem really would be two-dimensional. The right solution for position of the secondary antenna might then be found within Hatch's initial set of 188 potential solutions. Determining the right solution would be a simple matter of eliminating 187 false solutions by comparison with the third carrier phase measurement. As long as phase measurement errors are small enough, the two-step method based on near perfect measurements is satisfactory. Though there is some small perturbation in computed results, the right answer comes out in the end most of the time. Phase measurement errors of about two degrees RMS are usually tolerable.
Only one whole cycle value results in a surface that passes closer to a specific potential solution than any other whole cycle value. The problem is that phase measurements contain error, and geometric considerations amplify this error when measurements are processed in a computing apparatus. There is only one surface that passes closer to a specific potential solution than any other, but unfortunately, the surface that passes closest is often the wrong surface. Another surface farther away may be the right one. Not only can the surface be in the wrong place due to measurement error, Hatch's potential solution may be in the wrong place as well, due to error effects that are worse for the potential solution than the surface.
The supposed potential solution is actually a computational result that is often badly perturbed by phase measurement error combined with geometrical dilution of precision. A scissors effect can amplify measurement errors that distort the planes. Subsequently, the formation of intersections of lines with a sphere introduces a nonlinear operation on noisy data which greatly amplifies some of the errors. Hatch actually chooses the two satellites closest together in order to form an initial set with fewer than 188 points, whereas considerations of error sensitivity would dictate the opposite.
Hatch teaches that only one of the whole cycle values passes closer to a specific potential solution than any other. The two-step Hatch method prescribes that only the closest whole cycle value (from the additional satellite data) is selected for each of the potential solutions whereby the number of potential solutions is not increased. At some point, as phase measurement errors are increased, corresponding to less favorable operating conditions, the prescription begins picking the wrong whole cycle values a significant fraction of the time. Using Hatch's method, there is no way to pursue any option but the closest, and processing a phase measurement with the wrong whole cycle value added to it further accelerates the deterioration of computed results.
By comparison, all of the whole cycle values are tried as possibilities in the Knight method. An integer combination that looks very poor initially becomes more attractive as the solution progresses, eventually finishing as the best possible solution out of 10,000 or more. Every possible integer combination is pursued until, taken as a whole, it can be decided that the combination under development is less likely than another combination that has been completely finished and weighed with all satellite data included. The Knight method does not minimize the solution space dimensionally to the bare minimum and then restricts attention to an "initial set of solutions" obtained with only the data of the first measurements corresponding to that bare dimensionally. Most of the time, under real world conditions, the right answer simply is not to be found. The job of finding the right solution cannot be accomplished by avoiding the problem of large numbers.
Benjamin W. Remondi, reported the status of differential GPS (DGPS) accuracy and on-the-fly (OTF) kinematic GPS (KGPS) in a paper titled, "On-The-Fly Kinematic GPS Results Using Full-Wavelength Dual-Frequency Carrier Ranges".
The carrier phase ambiguity resolution problem has been the focus of a great deal of attention from research communities. In essence, the integer number of carrier cycles that existed between GPS receiver and satellite at the time that the signal was acquired must be determined. Direct range measurements, combined with the satellite geometry, allow the correct integer carrier phase ambiguities to be determined for a plurality of satellites tracked at two or more sites. Ambiguity resolution techniques that only use GPS measurements have become computationally efficient. The use of additional sensors such as a laser level, electronic distance meter, a compass, a tape, etc., provide valuable constraints that limit the number of possible integer ambiguities that need to be considered in a search for the correct set. For example see, INTEGRATED TERRESTRIAL SURVEY AND SATELLITE POSITIONING SYSTEM, filed Jul. 1, 1993, and issued as U.S. Pat. No. 5,471,218.
A method for carrier phase ambiguity resolution is described by Benjamin W. Remondi in U.S. Pat. No. 5,442,363, which was filed Aug. 4, 1994, and was issued Aug. 15, 1995. Such Patent was filed after the parent case in the present Application. The method described by Remondi was previously described in broader terms in "Kinematic GPS Results Without Static Initialization" NOAA Technical Memo NOS-55, May 1991. Such method takes advantage of the dual-frequency carrier phase data and L1 code data to obtain centimeter-level results. Such technique works best when full-cycle carrier phase data is available on L1 and L2 bands and when precise C/A-code is measured, although the claim is made that the method can work with single-frequency data too.
The code and the carrier phase are simultaneously measured at the reference and rover stations. Single-difference code and carrier phase measurements are formed between the stations and all the visible satellites. The time interval is set long enough to maximize the filtering time constant, but still short enough so that the ionospheric divergence is not too great. A reference code epoch is chosen so that the single-difference ranges can be adjusted to one another. Single-difference carrier phase is used to adjust the code ranges to the reference code epoch. An averaged code measurement is then formed from all the code observations in a time window. A best estimate rover location relative to the reference station can be determined from four or more averaged code values. Such best estimate forms the center of a search volume that is then constructed. A variety of methods are given for generating the search space. The Hatch method of using the minimum number of phase intersections to generate the search candidates is then used for L1 and L2 phase candidate locations. The L1 and L2 space points will be coincident with one another if they are correct, the incorrect candidates are culled. All this assumes that the ionospheric disturbance is not too great, and such is not a valid assumption for long baselines. The L1 and L2 space points that agree within a threshold maximum are accepted for the next stage. Triple difference processing is used to propagate the potential L1 and L2 ambiguity candidates. The L1, L2, and ionospheric-free residuals are studied, and accumulated statistics are generated. A ratio test is used to discern the two best candidates from a list. If sufficient separation cannot be achieved before a best candidate can be accepted, the process is repeated.
The prior art methods, particularly those described by Hatch, are weak when the satellite constellation geometry is poor, and positions corresponding to the L1 and L2 bands have to be computed to generate L1/L2 candidates. Remondi's use of height constraints to reduce the search space was conventional when he adopted it. The Remondi method is best suited to post-processing applications because the averaging needed for the starting point calculations can be generated from a block of stored data.
It is preferable to accumulate past data in the filter and not store in memory.